package com.LeeCode;

/**
 * 两个线段获得的最多奖品
 */

public class Code2555 {
    public static void main(String[] args) {
        int[] nums = {1, 1, 2, 2, 3, 3, 5};
        int k = 3;
        System.out.println(new Code2555().maximizeWin(nums, k));
    }

    public int maximizeWin(int[] prizePositions, int k) {
        int n = prizePositions.length;
        if (n == 0) return 0;

        int[] maxCoverage = new int[n + 1];
        int left = 0;
        int maxPrizes = 0;

        for (int right = 0; right < n; right++) {
            // 移动左指针，直到当前区间 <= k
            while (prizePositions[right] - prizePositions[left] > k) {
                left++;
            }
            // 当前以prizePositions[right]为结尾的线段覆盖的奖品数量
            int currentCover = right - left + 1;
            // maxCoverage[right + 1] 表示前right+1个奖品中单个线段的最大覆盖
            maxCoverage[right + 1] = Math.max(maxCoverage[right], currentCover);
            // 当前线段与之前最大线段的和
            maxPrizes = Math.max(maxPrizes, currentCover + maxCoverage[left]);
        }

        return maxPrizes;
    }
}
